package 动态规划.贪心算法;

import java.util.Arrays;
import java.util.Comparator;

//给你很多形如[start,end]的闭区间，请你设计一个算法，算出这些区间中最多有几个互不相交的区间。
public class 区间调度 {
    public static void main(String[] args) {
         int[][] ints={{1,2},{2,3}};
        int i = intervalScheduling(ints);
        System.out.println(i);
    }
    public static int intervalScheduling(int[][] ints){
        if (ints.length==0)
            return 0;
        //对ints的第二列进行升序排序
        Arrays.sort(ints, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[1]-b[1];
            }
        });
        int end=ints[0][1];
        int count=1;
        for (int[] m: ints) {
            if (m[0]>=end){
                count++;
                end=m[1];
            }
        }
        return count;
    }

}
